package __回溯算法

import "strings"

/*
https://leetcode.cn/problems/n-queens/

51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：
输入：n = 4
输出：[
[

	".Q..",
	"...Q",
	"Q...",
	"..Q."

],

[

	"..Q.",
	"Q...",
	"...Q",
	".Q.."

]
]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：[["Q"]]
*/
func solveNQueens(n int) [][]string {

	var res [][]string
	chessboard := make([][]string, n) //声明二维数组
	for i := 0; i < n; i++ {          //初始化棋盘
		chessboard[i] = make([]string, n)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			chessboard[i][j] = "." //每个位置先放置'.'
		}
	}

	var dfs func(int)
	dfs = func(row int) {
		if row == n { //如果row到达了最后一行, 说明当前摆放策略是可行的, 需要进行存储
			temp := make([]string, n)
			for i, rowStr := range chessboard {
				temp[i] = strings.Join(rowStr, "")
			}
			res = append(res, temp)
			return
		}
		for col := 0; col < n; col++ { //从第0列, 到第n列
			if isValid(n, row, col, chessboard) { //n:几*几的棋盘 row:当前行数 col:当前列数 chessboard:棋盘
				chessboard[row][col] = "Q" //当前位置符合条件, 那么放一个皇后
				dfs(row + 1)               //递归校验下一行
				chessboard[row][col] = "." //回溯
			}
		}
	}

	dfs(0) //从第0行开始
	return res
}

func isValid(n int, row int, col int, chessboard [][]string) bool {
	for i := 0; i < row; i++ { //同一列不能出现其它皇后
		if chessboard[i][col] == "Q" {
			return false
		}
	}

	//校验左斜方不能出现其它皇后
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if chessboard[i][j] == "Q" {
			return false
		}
	}
	//校验右斜方不能出现其它皇后
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if chessboard[i][j] == "Q" {
			return false
		}
	}

	return true
}
